package day1.BitAddMinusMultDiv;

/**
 * @author pacai
 * @version 1.0
 * 二进制实现加减乘除
 */
public class BitAddMinusMultDiv {
    public static int add(int a, int b) {
        int sum = a;
        while (b != 0) {//当没有进位时退出
            sum = a ^ b;//无进位相加
            b = (a & b) << 1;//进位信息
            a = sum;//无进位相加信息
        }
        return sum;
    }

    public static int negNum(int num) {
        return add(~num, 1);
    }

    public static int sub(int a, int b) {
        return add(a, negNum(b));
    }

    public static int mul(int a, int b) {
        int res = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                res = add(res, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return res;
    }

    public static boolean isNeg(int num) {
        return num < 0;
    }

    public static int div(int a, int b) {
        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int res = 0;
        for (int i = 30; i >= 0; i = sub(i, 1)) {
            if ((x >> i) >= b) {
                res |= 1 << i;//此时被除数可以减去除数乘左移i位(res * 2 ^ i)
                x = sub(x, y << i);//被除数要减去除过后的数（即b * 2 ^ i)
            }
        }
        return isNeg(a) ^ isNeg(b) ? negNum(res) : res;//同号返回res
    }

    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            if (b == negNum(1)) {
                return Integer.MAX_VALUE;//leedcode规定
            } else {
                //(a + 1) / b = c
                //a - b * c = d
                //d / b = e
                //ans = c + e
                int c = div(add(a, 1), b);
                return add(c, div(sub(a, mul(b, c)), b));
            }
        } else {
            return div(a, b);
        }
    }
}
